第一個要來看的公鑰加密演算法是 RSA。
記得我們在 DAY6 的時候介紹到 RC4 時提到一個人嗎，
設計RC4 的 Ron Rivest 就是RSA 的R，
他和其他兩人 Adi Shamir 和 Leonard Adleman 共同提出了 RSA 演算法。

今天比較硬一點（可能?）
因為要理解 RSA 的算法需要一點先備（仙貝）的小知識，
我們知道仙貝是用米做的，所以

質數 Prime numbers

我記得快一年前的一個晚上我在宿舍和室友爭論一件事，
我們在爭論為什麼數學家要浪費時間找一個非常大的質數，
就算找到了可以幹嘛？

你知道世界上目前發現最大的質數是多少嗎。

在2017年日本人甚至出版了一本書就叫做最大的質數，
他們花了719頁印完了上一個最大的質數。

我不知道其他的質數對數學家有什麼意義（他們甚至有快樂質數這種東西）
不過質數對 RSA 來說非常重要。

質因數分解

RSA的安全性建立在數字的質因數分解難度。
隨便講個數字，98好了，拿給一個國小小朋友要他做質因數分解應該都做得出來，
小朋友就會開始從2、3、5、7...
找遍所以質數（prime number）看能不能整除98，所以很幸運的他第一個2就找到了。

所以你發現質因數分解的困難度就在於你找到第幾個質數可以整除這個數。
那我們來試試這個：323。
所以一樣你從2開始找，找到17的時後 bingo!
你發現他可以整除，323=17×19，problem solved。

所以隨著質數越來越大，質因數分解的難度就會提高，
當我們將709×941時可以很容易地得到 667,169，而別人很難將667,169分解。
這就是 RSA 安全性的來源，而 RSA 使用的是非常大的質數。

接下來會頻繁用到 mod 的概念，如果忘記的話，可以（一定要）回去 DAY2 複習。
另外，運算中會使用到Euler's Phi function，

Euler's Phi function

Euler 念作「歐伊樂」，中文翻作歐拉或尤拉，18世紀瑞士數學家。
就是發現世界最美公式的那個( 崇拜 )，
他還有一堆奇奇怪怪公式。

歐拉函數是用來算「小於等於 n 的正整數中與 n 互質的數的數目」，寫作，
舉例來說：，因為小於5的數中1、2、3、4總共4個數字和5互質。

而在這裡我們會將兩個質數相乘在一起，
所以我們得知道這個公式：

不過不用擔心，畢竟我們沒有要探究原理，只是講一下怎麼算而已。

乘法反元素

n 的乘法反元素就是跟自己相乘之後會等於1，我們寫作。

最簡單的，在實數裡面 2 的乘法反元素就是 ，因為

所以你要說是除法也可以。

高中有學過矩陣的人就知道，矩陣的乘法反元素，也就是反矩陣，
並不像整數的乘法反元素這麼好求，反矩陣跟原本的矩陣也漲得一點都不像。
在這裡我們會需要計算在mod n 之下的乘法反元素，

什麼意思呢？

舉個例子：我們考慮一個所有運算都 mod 5 的集合裡面，
這個集合裡有{0, 1, 2, 3, 4}，5就是0，6就是1，一直下去，每個數字都除以5取餘數。

2和3互為乘法反元素，因為2×3 ≡ 6 (mod 5) ≡ 1 (mod 5)，（"≡"視同餘的符號，我們可以看成 "=" 就好）
4的乘法反元素就是自己，因為4×4 ≡ 16 (mod 5) ≡ 1 (mod 5)

在更大的模數之下，也就是mod n 的 n 很大時，乘法反元素並不容易看出來，
所以如果要用手算的話，會需要使用到「擴展歐幾里得算法（Extended euclidean algorithm）」。

不過我們都是依靠電腦的廢物吧（至少不是數學家?），
所以這種事就交給電腦來做就好了，
我們知道他在幹嘛就好了。

如果使用python 的話有個簡單的指令可以馬上得到乘法反元素。
奉上。

# inverse of a modulo n
pow(a,-1,n)

好了各位，我們已經有能力看懂 RSA 怎麼運作了，
我們，
明天再看...
(掰)

圖片來源：
https://www.ettoday.net/dalemon/post/33540
https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-1/
https://www.reddit.com/r/mathmemes/comments/c1prja/eulers_formulareimann_zetaeulers_identityanalytic/
https://www.reddit.com/r/memes/comments/atda9f/maths_can_be_whatever_i_want_it_to_be/